home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / intrvews / xgrab.lha / xgrab / doc / xgrab_intro.ms < prev    next >
Text File  |  1990-04-24  |  7KB  |  160 lines
  1. .\" GRAB Graph Layout and Browser System
  2. .\" 
  3. .\" Copyright (c) 1986, 1988 Regents of the University of California
  4. .\" Copyright (c) 1989, Tera Computer Company
  5. .\" 
  6. .\" Permission to use, copy, modify, and distribute this software and its
  7. .\" documentation for educational, research, and non-profit purposes and
  8. .\" without fee is hereby granted, provided that the above copyright 
  9. .\" notice appear in all copies and that both that copyright notice and
  10. .\" this permission notice appear in supporting documentation, and that
  11. .\" the name of the University of California not be used in advertising
  12. .\" or publicity pertaining to distribution of the software without 
  13. .\" specific, written prior permission.  Permission to incorporate this
  14. .\" software into commercial products can be obtained from the Campus 
  15. .\" Software Office, University of California, Berkeley, CA 94720.  
  16. .\" The University of California makes no representations about the 
  17. .\" suitability of this software for any purpose.  It is provided "as is" 
  18. .\" without express or implied warranty.
  19. .\" 
  20. .\" Permission to use, copy, modify, and distribute this software and its
  21. .\" documentation for educational, research, and non-profit purposes and
  22. .\" without fee is hereby granted, subject only to the condition that Tera
  23. .\" Computer Company makes no representation about the suitability of 
  24. .\" this software for any purpose.  It is provided "as is" without express or 
  25. .\" implied warranty.
  26. .\" 
  27. .\" Furthermore, portions of this system
  28. .\" Copyright (c) 1987, 1988, 1989 Stanford University
  29. .\"
  30. .\" Permission to use, copy, modify, distribute, and sell this software and its
  31. .\" documentation for any purpose is hereby granted without fee, provided
  32. .\" that the above copyright notice appear in all copies and that both that
  33. .\" copyright notice and this permission notice appear in supporting
  34. .\" documentation, and that the name of Stanford not be used in advertising or
  35. .\" publicity pertaining to distribution of the software without specific,
  36. .\" written prior permission.  Stanford makes no representations about
  37. .\" the suitability of this software for any purpose.  It is provided "as is"
  38. .\" without express or implied warranty.
  39. .\"
  40. .\" STANFORD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  41. .\" INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
  42. .\" IN NO EVENT SHALL STANFORD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  43. .\" CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
  44. .\" DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
  45. .\" OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
  46. .\" WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  47. .\"
  48. .\" (whew!)
  49. .\" 
  50. .TL
  51. Introduction to GRAB
  52. .AU
  53. Lawrence A. Rowe
  54. revised by Greg Barnes
  55. .AI
  56. Computer Science Division - EECS
  57. University of California
  58. Berkeley, CA 94720,   and
  59.  
  60. Tera Computer Company
  61. 400 N. 34th St., Suite 300
  62. Seattle, WA 98103,    respectively
  63. .PP
  64. Directed graphs are commonly used
  65. to represent information.  For example, in Computer Science graphs are
  66. used to represented program call-graphs, module dependency graphs, the
  67. fsa underlying an LR parser, and database designs.
  68. .PP
  69. GRAB was designed to display and edit arbitrary directed graphs.  A
  70. novel feature of \fIGRAB\fR is that it has an operation to layout a
  71. graph automatically.  The current implementation of this operation is
  72. based on an algorithm developed by Sugiyama, et.al.  [Sugiyama].  The
  73. objective of the algorithm is to minimize the number of edge crossings
  74. and to produce a layout that makes the graph easier to understand.  The
  75. initial implementation of this algorithm was done by Carl Meyer.  His
  76. Master's report [Meyer] describes the design goals for \fIGRAB\fR and
  77. presents a description of the algorithm that is much easier to
  78. understand than the description in [Sugiyama].
  79. .PP
  80. Michael Davis modified the layout heuristics used by the layout
  81. algorithm to straighten long edges, improve the placement of nodes on a
  82. level, and improve the routing of edges between nodes.  In addition,
  83. Davis modified the data structures to improve the run-time performance
  84. of the layout algorithm.  These changes are described in his Master's
  85. report [Davis].
  86. .PP
  87. The first implementation of the layout algorithm was on a VAX.  This
  88. implementation was ported to the Sun Microsystems M68K and included in
  89. a graph displayer and editor, called \fISUNGRAB\fR,  developed by
  90. Charles Spirakis and Michael Davis, and later on modified by Allen
  91. Tuan and Eli Messinger.
  92. .PP
  93. Greg Barnes ported the \fISUNGRAB\fR program to the X Window System, 
  94. Version 11, altering the layout algorithm slightly, the user interface
  95. extensively, and the name completely (to \fIXGRAB\fR).
  96. The source code, documentation, manual pages, and sample data
  97. files for this program are included in the parent of this directory.  
  98. The README file there describes how to compile the system.
  99. .PP
  100. [the following notes are about the sungrab system, not the xgrab system.
  101. Although I can't be sure, I believe the first improvement has already been
  102. accomplished.  Layouts should take seconds, not minutes, to perform.
  103. An in-core representation is still being used, however.]
  104. .PP
  105. We are continuing to improve and extend the \fISUNGRAB\fR system.  Some
  106. of the improvements and extensions currently being worked on are:
  107. .IP 1.
  108. The algorithms and data structures will be changed to make the system
  109. run faster.  We have layed out a graph with approximately 250 nodes and
  110. 1000 edges (the call-graph for \fISUNGRAB\fR itself).  This graph took
  111. 25 minutes to layout.  Loading the graph after it was layed out took
  112. over 8 minutes.  We want to speed the system up so we can operate on
  113. graphs with up to 1000 nodes.  Eventually, this will require modifying
  114. the system to run on graphs stored in a database system rather than the
  115. in-core representation currently used.
  116. .IP 2.
  117. The layout algorithm will be improved and changed to layout graphs
  118. incrementally so that interactive editing of the graph or the data
  119. represented by the graph (e.g., a source program) will not require the
  120. entire graph to be layed out again.  In addition, we have heuristics
  121. for improving the current layouts with which we want to experiment.
  122. .PP
  123. We also are hoping that early users of the system will offer
  124. suggestions for improvements.  Please send suggestions to me at the
  125. following address given above or e-mail to
  126. .IP
  127. \fBlarry@ingres.Berkeley.EDU\fR.
  128. .LP
  129. Bugs or problems installing and using the sungrab system should be sent to 
  130. .IP
  131. \fBgrab@ingres.Berkeley.EDU\fR.
  132. .LP
  133. Bugs or problems installing and using the xgrab system should be sent to 
  134. .IP
  135. \fBgreg@cs.washington.edu\fR.
  136. .SH
  137. References
  138. .LP
  139. .nf
  140. [Davis]        M. Davis
  141.         ``A Layout Algorithm for a Graph Browser.''
  142.         Masters Report, Comp. Sci. Div.-EECS, U.C. Berkeley
  143.         (May 1985).
  144.  
  145. [Meyer]        C. Meyer
  146.         ``A Brower for Directed Graphs.''
  147.         Masters Report, Comp. Sci. Div.-EECS, U.C. Berkeley
  148.         (Dec. 1983).
  149.  
  150. [Sugiyama]    K. Sugiyama, S. Tagawa, and M. Toda
  151.         ``Methods for Visual Understanding of Hierarchical Systems
  152.         Structures.''  IEEE Trans. on Sys. Man, and Cyb., SMC-11 (2)
  153.         (Feb. 1981).
  154. .SH
  155. Note
  156. .IP
  157. \fIX Window System\fR is a trademark of the Massachusetts Institute of 
  158. Technology
  159. .fi
  160.